package com.yangli.leecode.mashib.interview;

import java.util.*;

/**
 * @Description
 * @Author liyang
 * @Date 2023/3/6 15:48
 */
public class ThirtyTwo {
    public static void main(String[] args){

        System.out.println(ThirtyTwo.majorityElementOfK(new int[]{1, 3, 4, 5, 1, 1, 1, 5, 5, 5, 7, 5, 1, 2, 1, 5}, 3));

    }


    public static Set<Integer> majorityElementOfK(int[] arr, int k){
        if (k < 2 || arr.length / k <= 1) {
            return Collections.EMPTY_SET;
        }
        Map<Integer, Integer> hashMap = new HashMap<>();
        for (int num : arr) {
            if (hashMap.containsKey(num)) {
                hashMap.put(num, hashMap.get(num) + 1);
                continue;
            }
            if (hashMap.size() < k - 1) {
                hashMap.put(num, 1);
                continue;
            }
            removeCount(hashMap);
        }
        Map<Integer, Integer> reals = new HashMap<>();
        for (int i = 0; i < arr.length; i++) {
            int num = arr[i];
            if (hashMap.containsKey(num)) {
                if (reals.containsKey(num)) {
                    reals.put(num, reals.get(num) + 1);
                } else {
                    reals.put(num, 1);
                }
            }
        }
        for (Iterator<Integer> iterator = reals.keySet().iterator(); iterator.hasNext(); ) {
            Integer key = iterator.next();
            if (reals.get(key) <= (arr.length / k)) {
                reals.remove(key);
            }
        }


        return reals.keySet();

    }

    public static void removeCount(Map<Integer, Integer> hashMap){
        List<Integer> removeList = new ArrayList<>();
        for (Iterator<Integer> iterator = hashMap.keySet().iterator(); iterator.hasNext(); ) {
            Integer key = iterator.next();
            if (hashMap.get(key).equals(1)) {
                removeList.add(key);
                continue;
            }
            hashMap.put(key, hashMap.get(key) - 1);
        }
        for (Integer temp : removeList) {
            hashMap.remove(temp);
        }
    }


}
